package day_2022_7_to_8.day48;

import java.util.List;

/**
 * @author haomin
 * @date 2022/07/22 22:52
 **/
public class Day7_2_Num120_MinimumTotal {
    class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            //记录矩阵的行数
            int row = triangle.size();

            //记录最后一行数组的值（行数和列数相等）
            int[] cache = new int[row];
            for(int k = 0; k < row ; k++){
                cache[k] = triangle.get(row -1).get(k);
            }

            //从倒数第二行数组开始遍历
            for(int i = row -2; i>= 0; i--){
                for(int j = 0; j <= i; j++){
                    cache[j] = Math.min(cache[j],cache[j+1])
                            + triangle.get(i).get(j);
                }
            }
            return cache[0];
        }

//初始状态
// [
// [2],
// [3,4],
// [6,5,7],
// [4,1,8,3]]
//cache = []

// 初始化缓存数组后
// cache = [4,1,8,3]

//第一次j遍历完成之后
// [6,5,7]
// [4,1,8,3] ，这是初始化后的缓存数组
// cache = [7,6,10,3]
// 其中 7 = min(4,1)+6, 6 = min(1,8)+5, 10 = min(8,3)+7,3不是计算所得

//第二次j遍历完成之后
// [3,4]
// [7,6,10,3] 这是第一次计算之后的缓存数组
// cache = [9,10,10,3]
//其中 9 =  min(7,6)+3,10 = min(6,10)+4,10,3不是这次计算所得

//第三次j遍历完成之后
//[2]
//[9,10,10,3]
// cache = [11,10,10,3]
// 其中 9 = min(11,10)+2,10,10,3不是计算所得
//返回cache[0]

    }
}